#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef struct node
{
    int data;
    node *next;
} node;

node* buildlist ()
{
    node* phead = NULL;
    node* p = (node*) malloc(sizeof(node));
    if (p!=NULL) {
        phead = p;
        p->data = 1;
        p->next = NULL;
    } else {
        return NULL;
    }
    for (int i=2;i<20;i++) {
        node* tmp = (node*)malloc(sizeof(node));
        if (tmp!=NULL) {
            tmp->data=i;
            tmp->next = phead;
            phead = tmp;
        } else {
            assert(0);
        }
    }

    return phead;
}

bool deletelist(node* phead)
{
    node* p = phead;
    while (p) {
        node* tmp = p;
        p = p->next;
        free(tmp);
        tmp = NULL;
    }
    return true;
}

void printlist(node* head)
{
    node* p = head;
    while (p) {
        fprintf(stdout, "%d ", p->data);
        p = p->next;
    }
    fprintf(stdout, "\n");
}

node* revertlist(node* head)
{
    node* newhead = NULL;
    node* now = head;
    node* next = NULL;
    node* pre = NULL;
    while (now) {
        if (!now->next) newhead = now;
        next = now->next;
        now->next = pre;
        pre = now;
        now = next;
    }
    return newhead;
}

node* insert_to_head(node* head, node* tmp)
{
    tmp->next = head;
    return tmp;
}

node* sortlist_bubble(node* head)
{
    if (!head || head->next == NULL || head->next->next == NULL) {
        return NULL;
    }
    node* fake_head = (node*) malloc (sizeof(node));
    fake_head->data = 0;
    fake_head->next = head;
    node* f = NULL;
    node* p = NULL;
    node* x = NULL;
    node* y = NULL;
    while (fake_head->next->next != f) {
        for (p = fake_head; p->next->next != f; p = p->next) {
            if (p->next->data > p->next->next->data) {
                x = p->next;
                y = p->next->next;
                x->next = y->next;
                y->next = x;
                p->next = y;
            }
        }
        f = p->next;
    }
    head = fake_head->next;
    free(fake_head);
    fake_head = NULL;
    return head;
}

node* sortlist_bubble2(node* head)
{
    if (!head || head->next == NULL || head->next->next == NULL) {
        return NULL;
    }
    node* f = NULL;
    node* p = NULL;
    node* x = NULL;
    node* y = NULL;
    while (head->next != f) {
        if (head->data > head->next->data) {
            x = head->next;
            head->next = head->next->next;
            x->next = head;
            head = x;
        }
        for (p = head; p->next->next != f; p = p->next) {
            if (p->next->data > p->next->next->data) {
                x = p->next;
                y = p->next->next;
                x->next = y->next;
                y->next = x;
                p->next = y;
            }
        }
        f = p->next;
    }
    return head;
}

int main ()
{
    node* head = buildlist();
    printlist(head);
    node* newhead = head;
    //node* newhead = revertlist(head);
    //printlist(newhead);
    newhead = sortlist_bubble2(newhead);
    printlist(newhead);
    deletelist(newhead);
    return 0;
}
